The present invention relates generally to processing and displaying digital images. A digital image is a raster of rows and columns of picture elements, or xe2x80x9cpixels.xe2x80x9d The color of a given pixel is defined in accordance with a xe2x80x9ccolor space,xe2x80x9d which provides a data representation for a range of colors (a xe2x80x9ccolor gamutxe2x80x9d) in terms of basic color components (or xe2x80x9ccolorantsxe2x80x9d). A pixel""s color is generally represented by a series of bits (the xe2x80x9ccolor valuexe2x80x9d), with specific bits indicating the amount of each colorant used in the color. The specific colorants depend on the color system used. For example, in the CMYK color system, colors are represented as combinations of values for cyan (C), magenta (M), yellow (Y), and key (K) (generally black); in an RGB color system, colors are represented as combinations of values for red (R), green (G), and blue (B); and in the HSV color system, colors are represented as combinations of values for hue (H), saturation (S) and value (V). Thus, a 24-bit RGB data representation may allocate bits 0-7 to indicate the amount of red, bits 8-15 to indicate the amount of green, and bits 16-23 to indicate the amount of blue. Such a representation can produce a pixel in any one of nearly 17 million different pixel colors (i.e., the number of unique combinations of 256 intensity values of red, green, and blue). By contrast, systems that allocate fewer bits of memory to storing color data can produce only images having a limited number of colors. For example, an 8-bit color image can include only 256 different colors.
Although digital images are often created using 24 bits of color information, images are often compressed or xe2x80x9cquantizedxe2x80x9d to conserve memory and decrease processing times. A typical digital image, even one created using 24 bits to store color information, may include only a relatively small number of colors. For more complex images, quantization (usually from 24 bit to 8 bit color) necessarily results in the loss of color resolution, raising the questions what set or palette of colors to use to display the image (a xe2x80x9cdisplay palettexe2x80x9d), and how to map the remaining or xe2x80x9cmissingxe2x80x9d image colors into the display palette.
One approach is to use a predetermined display palette and a fixed mapping from image colors to display palette. For example, an RGB color space may be divided into 256 equal-sized color regions and one display palette color may be selected from each region. The image may then be mapped into the display palette, with the missing colors being mapped to the closest color in the display palette (measured by proximity in an RGB color space).
Another approach is to select the display palette based on the actual distribution of colors in the image (often called xe2x80x9cadaptive palettesxe2x80x9d). For example, a xe2x80x9cpopularity algorithmxe2x80x9d may be used to create a histogram of colors in the image and select the most frequent colors to use as the display palette. In this approach, the color space is again divided into a number of equal-sized regionsxe2x80x94for example, 32,768 or more regions, corresponding to 32 or more divisions on each color axis in an RGB color space. The image colors are mapped to the region they fall in, and the 256 most popular regions are selected. One display palette color is selected from each of these 256 regions, and the image is mapped to the display palette with missing colors being mapped to the closest color in the display palette.
In a related approach, the quantization algorithm begins with an initial histogram stored as a list of colors in the image. Upon reaching a predetermined memory limit, the algorithm defaults to a low resolution histogram of predetermined size. This low resolution histogram is then used to generate a palette of colors to display the image as described above.
Another alternative is the use of an xe2x80x9coctreexe2x80x9d algorithm to obtain a palette of the K most popular colors in the image, where K is a predetermined number of xe2x80x9cleavesxe2x80x9d in the tree. In this method, the colors of the image are sequentially read into the octree and associated color counts are stored in leaves. For each new color, if the tree has fewer than K leaves with non-zero counts, the color is filtered down the tree until it reaches the leaf corresponding to the color. If the tree already has K leaves, a set of leaves are merged to make room in the tree for the new color. After the entire image has thus been processed, the display palette consists of the set of representative colors associated with each leaf, and the image is mapped to that palette.
The invention provides methods for generating data structures representing the frequency with which colors occur in a collection of colors, such as occurs in a raster image, and apparatus (include computer program products) implementing or embodying the methods of the invention.
In general, in one aspect, the invention features a method of generating a data structure representing the frequency with which colors occur in a raster image. The method includes providing a list consisting essentially of first generation entries, each first generation entry having an associated color set of one or more colors, each first generation entry representing the frequency with which colors in the associated color set appear in the image, the color sets for all of the first generation entries being mutually non-intersecting; and combining first generation entries to form a list consisting essentially of second generation entries.
Implementations of the invention can include one or more of the following advantageous features. Each first generation entry and second generation entry includes an index identifying the color set. Each color set corresponds to a volume in a color space. The frequency is represented as a count. Each second generation entry has an associated second generation color set of one or more colors, each second generation entry representing the frequency with which colors in the associated color set appear in the image, the color sets for all of the second generation entries being mutually non-intersecting. Each second generation color set corresponds to a volume of the color space. All second generation color sets are of the same size. The method also includes using the list of second generation entries to generate a palette representing the colors in the image. The method also includes combining second generation entries to form a list consisting essentially of third generation entries. Each third generation entry has an associated third generation color set of one or more colors, where each third generation entry represents the frequency with which colors in the associated color set appear in the image, and the color sets for all of the third generation entries are mutually non-intersecting. The method also includes using the list of third generation entries to generate a palette representing the colors in the image.
In general, in another aspect, the invention features a method of generating a histogram for a collection of colors in which any color may occur zero, one, or more times, where the colors are selected from a range of color values in a color space. The method includes dividing the range of color values using an first set of divisions to define a first set of disjoint, uniform volumes in the color space; providing a first list consisting essentially of first generation entries, each first generation entry being associated with exactly one distinct volume of the first set of volumes; storing in an entry frequency data representing the frequency with which a color value within the associated volume occurs in the collection of colors; dividing the range of color values using a second set of divisions to define a second set of disjoint, uniform volumes in the color space; and creating a second list from the first list, the second list consisting essentially of second generation entries, each second generation entry being associated with exactly one distinct volume of the second set of volumes and storing combined frequency data for color values in the associated volume.
Implementations of the invention can include one or more of the following advantageous features. Each division is orthogonal to an axis of the color space. The second set of divisions is a proper subset of the first set of divisions (i.e., the second set includes fewer elements than the first set). The second set of divisions is the first set of divisions minus a subset consisting of mutually parallel divisions. The second set of divisions is the first set of divisions minus a subset of divisions, and for each axis of the color space, the subset includes at least one division orthogonal to the axis. The color space is an RGB (red green blue) color space and each division is a plane orthogonal to either the red axis, the green axis, or the blue axis of the color space. Each volume in the second set of volumes is the union of two or more volumes in the first set of volumes. The method further includes dividing the range of color values using a third set of divisions to define a third set of disjoint, uniform volumes in the color space; and creating a third list from the second list, the third list consisting essentially of third generation entries, each third generation entry being associated with exactly one distinct volume of the third set of volumes and storing combined frequency data for color values in the associated volume.
In general, in another aspect, the invention features a computer program on a computer-readable medium for generating a data structure representing the frequency with which colors occur in a collection of colors in which any color may occur zero, one, or more times, and the colors are selected from a range of color values in a color space. The program includes instructions to divide the range of color values using an first set of divisions to define a first set of disjoint, uniform volumes in the color space; to provide a first list consisting essentially of first generation entries, each first generation entry being associated with exactly one distinct volume in the first set of volumes; to store in an entry frequency data representing the frequency with which a color value within the volume associated with the entry occurs in the collection of colors; to divide the range of color values using a second set of divisions to define a second set of disjoint, uniform volumes in the color space; and to create a second list from the first list, the second list consisting essentially of second generation entries, each second generation entry being associated with exactly one distinct volume of the second set of volumes and storing combined frequency data for color values in the associated volume.
Implementations of the invention can include one or more of the following advantageous features. The program further includes instructions to divide the range of color values using a third set of divisions to define a third set of disjoint, uniform volumes in the color space; and to create a third list from the second list, the third list consisting essentially of third generation entries, each third generation entry being associated with exactly one distinct volume of the third set of volumes and storing combined frequency data for color values in the associated volume. The program further includes instructions to use the third list to generate a palette representing the color values in an image defining the collection of colors.
In general, in another aspect, the invention features a method of generating a histogram for a collection of colors in which any color may occur zero, one, or more times, where the colors are selected from a range of color values in a color space. The method includes (a) dividing the color space into a set of disjoint volumes, each volume encompassing one or more colors in the color space; (b) for each occurrence of a color in the collection of colors, (i) identifying the volume in which the color is found, (ii) providing an entry associated with the identified volume in a list of entries, each entry in the list being associated with exactly one distinct volume and having frequency data representing the frequency with which colors in the associated volume occur in the collection, and (iii) updating the frequency data of the entry; (c) before all occurrences in the collection have been processed, (i) redividing the color space into a current set of larger, disjoint volumes, each larger volume being the union of two or more smaller volumes of the previously-defined set of volumes, (ii) combining original entries in the list so that each resulting entry in the list is associated with exactly one distinct volume of the current set of volumes and combines the frequency data of the original entries that were combined to form the resulting entry, and (iii) continuing the processing of step (b); and (d) generating a color frequency histogram from the newest entries in the list.
Implementations of the invention can include one or more of the following advantageous features. Step (c) is performed multiple times. The method further includes detecting a performance condition; and performing step (c) when the performance condition is detected. The performance condition is a memory limit condition. The performance condition is a list search time condition. The performance condition is a list insert time condition.
Among the advantages of the invention are the following. Using a histogram of colors in the original image to generate a display palette results in display palettes that more accurately reflect the colors in the original image. As a result, distortion of colors in the displayed image is minimized. In addition, varying the resolution of the histogram in response to a performance or quality condition, such as a limit in available memory, processing speed to search or insert new colors into the histogram, avoids arbitrary and unnecessary loss of color information during color quantization. Instead, loss of color information is minimized by gradually decreasing color resolution only as much as necessary to address performance constraints, producing a displayed image with better color resolution.
Another advantage is that the histogram can be stored as a sorted sparse list of colors in the image. This can result in significant storage savings and rapid processing times. In particular, this provides for the rapid identification of an entry that includes a given color in the image.
Another advantage is that color resolution may be decreased in any one or more dimensions in a color space. This selectivity in the loss of color resolution provides the opportunity to preserve resolution in dimensions that are more significant in the image.
Another advantage of the invention is that it is not restricted to any particular color space.
Other features and advantages will become apparent from the following description, including the drawings and the claims.